package leetcode101.mathematical_problem;

import java.util.Random;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code9
 * @Description 382. 链表随机节点
 * 给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
 * <p>
 * 进阶:
 * 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
 * <p>
 * 示例:
 * <p>
 * // 初始化一个单链表 [1,2,3].
 * ListNode head = new ListNode(1);
 * head.next = new ListNode(2);
 * head.next.next = new ListNode(3);
 * Solution solution = new Solution(head);
 * <p>
 * // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
 * solution.getRandom();
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-26 10:20
 */
public class Code9 {
    public static void main(String[] args) {

    }

    class Solution {

        ListNode head = null;
        Random random = new Random();

        /**
         * @param head The linked list's head.
         *             Note that the head is guaranteed to be not null, so it contains at least one node.
         */
        public Solution(ListNode head) {
            this.head = head;
        }

        /**
         * Returns a random node's value.
         */
        public int getRandom() {
            int res = -1, count = 0;
            for (ListNode cur = this.head; cur!= null; cur = cur.next) {
                if (this.random.nextInt(count++) == 0) {
                    res = cur.val;
                }
            }
            return res;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

}


